package fun.ticsmyc.question.dp;

import fun.ticsmyc.tools.TreeNode;

import java.util.Arrays;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.question.dp
 * @date 2021-02-07 12:49
 */
public class 打家劫舍 {

    /**
     * 线性dp
     */
    class 打家劫舍1 {
        public int rob(int[] nums) {
            int n =nums.length;
            if(n==0) return 0;
            if(n==1) return nums[0];

            int[] dp = new int[nums.length];
            dp[0]=nums[0];
            dp[1] = Math.max(nums[0],nums[1]);
            for(int i=2;i<nums.length;++i){
                dp[i] = Math.max(dp[i-2]+nums[i] , dp[i-1]);
            }
            return dp[nums.length-1];
        }
    }

    /**
     * 首尾相连的dp （对子数组dp两次）
     */
    class 打家劫舍2 {
        public int rob(int[] nums) {
            if(nums.length ==1){
                return nums[0];
            }
            return Math.max(fun(Arrays.copyOfRange(nums,0,nums.length-1)), fun(Arrays.copyOfRange(nums,1,nums.length)));
        }

        public int fun(int[] nums){
            if(nums.length==1){
                return nums[0];
            }
            int[] dp = new int[nums.length];
            dp[0]=nums[0];
            dp[1] = Math.max(nums[0],nums[1]);
            for(int i=2;i<nums.length;++i){
                dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
            }
            return dp[nums.length-1];
        }
    }

    /**
     * 树形dp
     */
    class 打家劫舍3 {
        public int rob(TreeNode root) {
            ReturnType r = fun(root);
            return Math.max(r.include,r.declude);
        }

        public ReturnType fun(TreeNode root){
            if(root ==null){
                return new ReturnType(0,0);
            }
            ReturnType left = fun(root.left);
            ReturnType right = fun(root.right);
            int i = left.declude+right.declude +root.val; //偷这个节点，则左右孩子不能偷
            int d = left.max+right.max; //不偷这个节点，左右孩子任意偷，取最大就行
            return new ReturnType(i,d);
        }

        private class ReturnType{
            int include; //偷这个节点时的最大收益
            int declude; //不偷这个节点的最大收益
            int max ;
            public ReturnType(int i,int d){
                this.include =i;
                this.declude=d;
                this.max = Math.max(i,d);
            }
        }
    }
}
